/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution395 {

    public static void main(String args[]) {
        Solution395 s = new Solution395();
        System.out.println(s.longestSubstring("aaaaabbbbbcc", 3));
    }

    public int longestSubstring(String s, int k) {
        int[] mp = new int[26];
        for(int i = 0 ; i < s.length() ; i ++){
            mp[s.charAt(i) - 'a'] ++;
        }
        return cal(mp, s, k);
    }

    public int cal(int[] mp, String s, int k){
        if(check(mp, s, k)){
            return s.length();
        }
        int l = 0;
        int maxv = 0;
        while(l < s.length()) {
            int[] cmp = new int[26];
            while (l < s.length() && mp[s.charAt(l) - 'a'] < k) {
                l++;
            }
            if(l < s.length()) {
                cmp[s.charAt(l) - 'a']++;
            }
            int r = l + 1;
            while(r < s.length() && mp[s.charAt(r) - 'a'] >= k){
                cmp[s.charAt(r) - 'a'] ++;
                r ++;
            }
            if(l < s.length()) {
                maxv = Math.max(cal(cmp, s.substring(l, r), k), maxv);
            }
            l = r;
        }
        return maxv;
    }

    public boolean check(int[] mp, String s, int k){
        for(int i = 0 ;i < 26 ; i ++){
            if(mp[i] != 0 && mp[i] < k){
                return false;
            }
        }
        return true;
    }
}
